package cn.jzq.sort;


import cn.jzq.util.ArrayTool;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/*
 *  插入排序 时间复杂度 O(n^2)
 *  最优复杂度：当输入数组就是排好序的时候，复杂度为O(n)，而快速排序在这种情况下会产生O(n^2)的复杂度。
 *  最差复杂度：当输入数组为倒序时，复杂度为O(n^2)
 *  插入排序比较适合用于“少量元素的数组”。
 * 其实插入排序的复杂度和逆序对的个数一样，当数组倒序时，逆序对的个数为n (n - 1) / 2，因此插入排序复杂度为 O(n^2)。
 *  InsertionSort(A)
 *
 *	for j = 2 to A.length												C1					n
 *		key = A[j]														C2					n - 1
 *		//InsertA[j] into the sorted sequence A[1..j-1]					C3					n - 1
 *		i = j -1														C4					n - 1
 *		while i > 0 and A[i] > key										C5					n * (n + 1) / 2 - 1
 *			A[i + 1] = A[i]												C6					n * (n - 1) / 2 - 1
 *			i = i -1													C7					n * (n - 1) / 2 - 1
 *		A[i + 1] = key													C8					n - 1
 */
public class InsertionSort
{
    /**
     * 普通插入排序
     */
    public static void insertionSort(Integer[] array)
    {
        for (int j = 1; j < array.length; j++)
        {
            int key = array[j]; // 要插入的值
            // 将key和循环不变式A[1...j - 1]作比较
            int i = j - 1;
            while (i >= 0 && array[i] > key)    // asc 升序
            {
                array[i + 1] = array[i]; //将大于key的值右移一位
                i--;
            }
            array[i + 1] = key; //插入key
        }
    }


    /**
     * @param array 需要排序的数组
     * @param p     起始索引
     * @param q     结束索引
     */
    public static void recursionInsertionSort(Integer[] array, int p, int q)
    {
        if (p < q)
        {
            recursionInsertionSort(array, p, q - 1);
            insert(array, p, q - 1);
        }
    }

    /**
     * @param p 开始索引
     * @param q 结束索引
     */
    public static void insert(Integer[] array, int p, int q)
    {
        int key = array[q]; // 需要排序的值
        int i = q - 1;
        while (i >= 0 && array[i] > key)
        {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = key;
    }


    public static void test(Integer[] str)
    {
        System.out.println(Arrays.toString(str));
    }


    /**
     *  进行耗时比较
     */
    public static void main(String[] args)
    {
        //int[] arr2 = new int[]{3, 4, 1, -2, 5, -5, 0};
        Integer[] array = ArrayTool.getRandomArray(1234, 100);

        Long resultOne = Long.valueOf("0");
        Long resultTwo = Long.valueOf("0");
        for (int i = 0; i < 1000; i++)
        {
            Long startTime = System.currentTimeMillis();
            insertionSort(array);
            Long endTime = System.currentTimeMillis();
            resultOne += endTime - startTime;

            // 打乱数组
            array = ArrayTool.shuffle(array);

            startTime = System.currentTimeMillis();
            recursionInsertionSort(array, 0, array.length);
            endTime = System.currentTimeMillis();
            resultTwo += endTime - startTime;

            array = ArrayTool.shuffle(array);
        }

        System.out.println("使用普通插入排序耗时 : " + resultOne + "ms");
        System.out.println("使用递归插入排序耗时 : " + resultTwo + "ms");

    }
}
